0001    //
0002    //  BigUInt Bitwise Ops.swift
0003    //  BigInt
0004    //
0005    //  Created by Károly Lőrentey on 2016-01-03.
0006    //  Copyright © 2016 Károly Lőrentey. All rights reserved.
0007    //
0008    
0009    import Foundation
0010    
0011    
0012    extension BigUInt {
0013        //MARK: Bitwise Operations
0014    
0015        /// The minimum number of bits required to represent this integer in binary.
0016        ///
0017        /// - Returns: floor(log2(2 * self + 1))
0018        /// - Complexity: O(1)
0019        public var width
BigInt.swift:147
        return PlaygroundQuickLook.Text(text + " (\(self.abs.width) bits)")
BigUInt Data.swift:55
        let byteCount = (self.width + 7) / 8
BigUInt Radix Conversion.swift:135
        return PlaygroundQuickLook.Text(text + " (\(self.width) bits)")
BigUInt Random.swift:54
        let width = limit.width
BigUInt Square Root.swift:20
    var x = BigUInt(1) << ((value.width + 1) / 2)
: Int {
0020            guard count > 0 else { return 0 }
0021            return count * Digit.width - self[count - 1].leadingZeroes
0022        }
0023    
0024        /// The number of leading zero bits in the binary representation of this integer in base `2^Digit.width`.
0025        /// This is useful when you need to normalize a `BigUInt` such that the top bit of its most significant digit is 1.
0026        ///
0027        /// - Note: 0 is considered to have zero leading zero bits.
0028        /// - Returns: A value in `0...(Digit.width - 1)`.
0029        /// - SeeAlso: width
0030        /// - Complexity: O(1)
0031        public var leadingZeroes
BigUInt Division.swift:128
        let z = y.leadingZeroes
: Int {
0032            guard count > 0 else { return 0 }
0033            return self[count - 1].leadingZeroes
0034        }
0035    
0036        /// The number of trailing zero bits in the binary representation of this integer.
0037        ///
0038        /// - Note: 0 is considered to have zero trailing zero bits.
0039        /// - Returns: A value in `0...width`.
0040        /// - Complexity: O(count)
0041        public var trailingZeroes
BigUInt GCD.swift:22
        let az = a.trailingZeroes
BigUInt GCD.swift:23
        let bz = b.trailingZeroes
BigUInt GCD.swift:30
            x >>= x.trailingZeroes
BigUInt Prime Test.swift:46
        let r = dec.trailingZeroes
: Int {
0042            guard count > 0 else { return 0 }
0043            let i = self.indexOf { $0 != 0 }!
0044            return i * Digit.width + self[i].trailingZeroes
0045        }
0046    }
0047    
0048    //MARK: Bitwise Operators
0049    
0050    /// Return the ones' complement of `a`.
0051    ///
0052    /// - Complexity: O(a.count)
0053    @warn_unused_result
0054    public prefix func ~(a: BigUInt) -> BigUInt {
0055        return BigUInt(a.map { ~$0 })
0056    }
0057    
0058    /// Calculate the bitwise OR of `a` and `b` and return the result.
0059    ///
0060    /// - Complexity: O(max(a.count, b.count))
0061    @warn_unused_result
0062    public func | (a: BigUInt, b: BigUInt) -> BigUInt {
0063        var result = BigUInt()
0064        for i in (0 ..< max(a.count, b.count)).reverse() {
0065            result[i] = a[i] | b[i]
0066        }
0067        return result
0068    }
0069    
0070    /// Calculate the bitwise AND of `a` and `b` and return the result.
0071    ///
0072    /// - Complexity: O(max(a.count, b.count))
0073    @warn_unused_result
0074    public func & (a: BigUInt, b: BigUInt) -> BigUInt {
0075        var result = BigUInt()
0076        for i in (0 ..< max(a.count, b.count)).reverse() {
0077            result[i] = a[i] & b[i]
0078        }
0079        return result
0080    }
0081    
0082    /// Calculate the bitwise OR of `a` and `b` and return the result.
0083    ///
0084    /// - Complexity: O(max(a.count, b.count))
0085    @warn_unused_result
0086    public func ^ (a: BigUInt, b: BigUInt) -> BigUInt {
0087        var result = BigUInt()
0088        for i in (0 ..< max(a.count, b.count)).reverse() {
0089            result[i] = a[i] ^ b[i]
0090        }
0091        return result
0092    }
0093    
0094    /// Calculate the bitwise OR of `a` and `b`, and store the result in `a`.
0095    ///
0096    /// - Complexity: O(max(a.count, b.count))
0097    public func |= (inout a: BigUInt, b: BigUInt) {
0098        a = a | b
0099    }
0100    
0101    /// Calculate the bitwise AND of `a` and `b`, and store the result in `a`.
0102    ///
0103    /// - Complexity: O(max(a.count, b.count))
0104    public func &= (inout a: BigUInt, b: BigUInt) {
0105        a = a & b
0106    }
0107    
0108    /// Calculate the bitwise XOR of `a` and `b`, and store the result in `a`.
0109    ///
0110    /// - Complexity: O(max(a.count, b.count))
0111    public func ^= (inout a: BigUInt, b: BigUInt) {
0112        a = a ^ b
0113    }
0114    
0115